package com.linzm.leetcode.mid.tree.层次遍历;

import java.util.*;

/**
 * @Author zimingl
 * @Date 2023/2/20 23:21
 * @Description: 给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 */
public class LevelOrder107 {
    public static void main(String[] args) {
        LevelOrder107 levelOrder107 = new LevelOrder107();
        List<List<Integer>> lists = levelOrder107.levelOrderBottom2(TreeNode.getTree());
        System.out.println(lists);
    }

    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> list = new ArrayList<>();
            int len = queue.size();
            while (len > 0) {
                TreeNode treeNode = queue.poll();
                list.add(treeNode.val);
                if (treeNode.left != null) {
                    queue.offer(treeNode.left);
                }
                if (treeNode.right != null) {
                    queue.offer(treeNode.right);
                }
                len--;
            }
            res.add(list);
        }
        Collections.reverse(res);
        return res;
    }

    public List<List<Integer>> levelOrderBottom2(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        List<List<Integer>> res = new ArrayList<>();
        dfs(root, 0, res);
        Collections.reverse(res);
        return res;
    }

    private void dfs(TreeNode root, int depth, List<List<Integer>> res) {
        if (root == null) return;
        depth++;
        if (res.size() < depth) {
            ArrayList<Integer> list = new ArrayList<>();
            res.add(list);
        }
        res.get(depth - 1).add(root.val);
        dfs(root.left, depth, res);
        dfs(root.right, depth, res);
    }
}
